package cn.zhl.tree.brst;

import cn.zhl.tree.binarysearch.BinarySearchTree;

import java.util.Comparator;

/**
 * @program: demos
 * @description:
 * @author: 刘振华
 * @create: 2020-05-15 10:08
 **/
public class BinaryRotateSearchTree<E> extends BinarySearchTree<E> {
	public BinaryRotateSearchTree() {
	}

	public BinaryRotateSearchTree(Comparator<E> comparator) {
		super(comparator);
	}

	//左旋转
	protected void rotateLeft(Node grand){
		Node parent = grand.right;
		Node child = parent.left;

		grand.right = child;
		parent.left = grand;

		afterRotate(grand,parent,child);
	}
	//右旋转
	protected void rotateRight(Node grand){
		Node parent = grand.left;
		Node child = parent.right;

		grand.left = child;
		parent.right = grand;

		afterRotate(grand,parent,child);
	}

	protected void afterRotate(Node grand,Node parent,Node child){
		parent.parent = grand.parent;
		if(grand.isLeftChild()){
			grand.parent.left = parent;
		}else if(grand.isRightChild()){
			grand.parent.right = parent;
		}else {
			root = parent;
		}
		if(child != null) {
			child.parent = grand;
		}
		grand.parent = parent;
	}

}
